home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 311_01 / sort.c < prev    next >
C/C++ Source or Header  |  1990-04-21  |  16KB  |  675 lines
  1. /****************************************************************************/
  2. /*                                                                          */
  3. /*                 S O R T  -  Callable Sort Facility                       */
  4. /*                             (c) 1987-1990 Ken Harris                     */
  5. /*                                                                          */
  6. /****************************************************************************/
  7. /*                                                                          */
  8. /*      This software is made available on an AS-IS basis. Unrestricted     */
  9. /*      use is granted provided that the copyright notice remains intact.   */
  10. /*      The author makes no warranties expressed or implied.                */
  11. /*                                                                          */
  12. /****************************************************************************/
  13.  
  14. char *copywrite = "sort v1.3 (c) 1987-1990  Ken Harris";
  15.  
  16. #include "dblib.h"
  17.  
  18. #define SORT_CLOSED          0
  19. #define SORT_OPEN         1
  20. #define SORT_DONE         2
  21. #define SORT_EOF             3
  22. #define MIN_BUFFER_SIZE   1000
  23. #define MAX_BUFFER_SIZE  32000
  24.  
  25. struct sort_buffer
  26. {    int   sb_file;            /* file descriptor        */
  27.     long  sb_fcnt;            /* file block count        */
  28.     long  sb_fpos;            /* file position        */
  29.     char *sb_badr;            /* buffer address        */
  30.     long  sb_bsiz;            /* buffer size in bytes     */
  31.     long  sb_rsiz;            /* buffer size in records    */
  32.     long  sb_rcnt;            /* current record count     */
  33.     char *sb_radr;            /* current record address    */
  34. };
  35.  
  36. struct key_field
  37. {    struct key_field *kf_next;    /* next key field        */
  38.     char   kf_type;         /* field type  'A' = Ascii    */
  39.                     /*           'I' = Integer    */
  40.                     /*           'U' = Unsigned    */
  41.     char   kf_seq;            /* sort order  'A' = Ascending    */
  42.                     /*           'D' = Descending */
  43.     int    kf_pos;            /* starting position        */
  44.     int    kf_size;         /* field size            */
  45. };
  46.  
  47. static int  sfile1;            /* temp file #1         */
  48. static int  sfile2;            /* temp file #2         */
  49. static int  sfile3;            /* temp file #3         */
  50.  
  51. static int  sort_state = 0;        /* current state of the sort    */  
  52.                     /* 0 = Sort not initialized    */
  53.                     /* 1 = Sort is    initialized    */
  54.                     /* 2 = Sort has been done    */
  55.  
  56. static int  sort_rec_size;        /* Size of user data record    */
  57. static long sort_rec_cnt;        /* Record Count         */
  58. static int  sort_key_size;        /* Size of user key        */
  59. static int  sort_krec_size;        /* Size of key + control info    */   
  60. static long sort_merge_cnt;        /* count records in merge pass    */
  61. static long sort_next_fpos;        /* position of next file block    */
  62. static struct key_field *key_spec=NULL; /* sort key specs        */
  63. static char *sort_key_rec;
  64.  
  65. static struct sort_buffer sbuf1;    /* Sort buffer #1        */
  66. static struct sort_buffer sbuf2;    /* Sort buffer #2        */
  67. static struct sort_buffer sbuf3;    /* Sort buffer #3        */
  68.  
  69. #ifdef ANSI
  70.     static one_merge_pass();
  71.     static char *sort_read(struct sort_buffer *);
  72.     static merge_write(struct sort_buffer *);
  73.     static sort_close();
  74.     static sort_write(int, char *, int);
  75.     static sort_error(char *);
  76. #else
  77.     static one_merge_pass();
  78.     static char *sort_read();
  79.     static merge_write();
  80.     static sort_close();
  81.     static sort_write();
  82.     static sort_error();
  83. #endif
  84.  
  85. long lseek();
  86.  
  87. /*
  88.  *    sort_init  -  Initialize the sort data
  89.  */
  90.  
  91. sort_init(rec_size, spec_str)
  92.  int   rec_size;
  93.  char *spec_str;
  94. {
  95. #ifdef MSC
  96.         unsigned _memavl();
  97. #endif
  98. #ifdef TURBO
  99.     unsigned coreleft();
  100. #endif
  101.         long  buf_size;
  102.         char *calloc();
  103.  
  104.     if (sort_state != SORT_CLOSED)
  105.         sort_error("Sort Already Initialized");
  106.  
  107.     sort_rec_size    = rec_size;
  108.     bld_key_spec(spec_str);
  109.  
  110.         sort_krec_size  = sort_key_size + sizeof(long);
  111.     sort_krec_size += sort_krec_size % 2;
  112.     sort_rec_cnt    = 0;
  113.  
  114.         sort_key_rec = (char *) calloc(1,sort_key_size);
  115.  
  116. #ifdef ULTRIX
  117.         sfile1 = open("SORT1.TMP", O_CREAT|O_RDWR, S_IREAD|S_IWRITE);
  118.         sfile2 = open("SORT2.TMP", O_CREAT|O_RDWR, S_IREAD|S_IWRITE);
  119.         sfile3 = open("SORT3.TMP", O_CREAT|O_RDWR, S_IREAD|S_IWRITE);
  120. #endif
  121. #ifdef SYSV
  122.         sfile1 = open("SORT1.TMP", O_CREAT|O_RDWR, S_IREAD|S_IWRITE);
  123.         sfile2 = open("SORT2.TMP", O_CREAT|O_RDWR, S_IREAD|S_IWRITE);
  124.         sfile3 = open("SORT3.TMP", O_CREAT|O_RDWR, S_IREAD|S_IWRITE);
  125. #endif
  126. #ifdef MSC
  127.         sfile1 = open("SORT1.TMP", O_CREAT|O_RDWR|O_BINARY, S_IREAD|S_IWRITE);
  128.         sfile2 = open("SORT2.TMP", O_CREAT|O_RDWR|O_BINARY, S_IREAD|S_IWRITE);
  129.         sfile3 = open("SORT3.TMP", O_CREAT|O_RDWR|O_BINARY, S_IREAD|S_IWRITE);
  130. #endif
  131. #ifdef TURBO
  132.         sfile1 = open("SORT1.TMP", O_CREAT|O_RDWR|O_BINARY, S_IREAD|S_IWRITE);
  133.         sfile2 = open("SORT2.TMP", O_CREAT|O_RDWR|O_BINARY, S_IREAD|S_IWRITE);
  134.         sfile3 = open("SORT3.TMP", O_CREAT|O_RDWR|O_BINARY, S_IREAD|S_IWRITE);
  135. #endif
  136.  
  137.     if (sfile1 < 0 || sfile2 < 0 || sfile3 < 0)
  138.         sort_error("Can't Open Temp Files");
  139.  
  140. #ifdef ULTRIX
  141.     buf_size  = MAX_BUFFER_SIZE;
  142. #endif
  143. #ifdef SYSV
  144.     buf_size  = MAX_BUFFER_SIZE;
  145. #endif
  146. #ifdef MSC
  147.         buf_size  = _memavl();
  148. #endif
  149. #ifdef TURBO
  150.     buf_size  = coreleft();
  151. #endif
  152.     if (buf_size > MAX_BUFFER_SIZE) buf_size = MAX_BUFFER_SIZE;
  153.     buf_size  = (buf_size * 3)/4;
  154.     buf_size -= buf_size % sort_krec_size;
  155.  
  156.     if (buf_size < MIN_BUFFER_SIZE)
  157.         sort_error("Insufficient Memory");
  158.  
  159.         sbuf1.sb_badr = (char *) calloc(1,buf_size);
  160.     sbuf1.sb_bsiz = buf_size;
  161.     sbuf1.sb_rsiz = buf_size/sort_krec_size;
  162.     sbuf1.sb_radr = sbuf1.sb_badr;
  163.     sbuf1.sb_rcnt = 0;
  164.  
  165.     sort_state = SORT_OPEN;
  166. }                      
  167.  
  168. /*
  169.  *    bld_key_spec  -  Build Sort Key Spec
  170.  */
  171. bld_key_spec(s)
  172.  char *s;
  173. {
  174.         struct  key_field *f;
  175.         char   *calloc(), ch;
  176.  
  177.     sort_key_size = 0;
  178.     f = key_spec  = NULL;
  179.     while (*s)
  180.     {
  181.         if (!key_spec)
  182.                         key_spec = f = (struct key_field *) calloc(1,sizeof(struct key_field));
  183.         else
  184.                 {       f->kf_next = (struct key_field *) calloc(1,sizeof(struct key_field));
  185.             f = f->kf_next;
  186.         }
  187.  
  188.         f->kf_next = NULL;
  189.         ch = *s++;
  190.         if (islower(ch)) ch = toupper(ch);
  191.         if (ch=='A' || ch=='D')
  192.             f->kf_seq = ch;
  193.         else
  194.             sort_error("Invalid Key Spec - Unknown Sequence");
  195.  
  196.         ch = *s++;
  197.         if (islower(ch)) ch = toupper(ch);
  198.         if (ch=='A' || ch=='I' || ch=='U' || ch=='R')
  199.             f->kf_type = ch;
  200.         else
  201.             sort_error("Invalid Key Spec - Unknown Field Type");
  202.  
  203.         f->kf_pos=0;
  204.         while (isdigit(*s))
  205.             f->kf_pos = 10 * f->kf_pos + (*s++ - '0');
  206.  
  207.         if (f->kf_pos < 1)
  208.             sort_error("Invalid Sort Spec - Invalid Starting Position");
  209.  
  210.         if (*s++ != '.')
  211.             sort_error("Invalid Sort Spec - Missing Field Size");
  212.  
  213.         f->kf_size=0;
  214.         while (isdigit(*s))
  215.             f->kf_size = 10 * f->kf_size + (*s++ - '0');
  216.              
  217.         sort_key_size += f->kf_size;
  218.  
  219.         if (f->kf_pos + f->kf_size - 1 > sort_rec_size)
  220.             sort_error("Invalid Sort Spec - Field Exceeds Record");
  221.  
  222.         if (*s==',') s++;
  223.     }
  224. }
  225.  
  226. /*
  227.  *    sort_release  -  Release a record to the sort
  228.  */
  229.  
  230. sort_release(data)
  231.  char *data;
  232. {
  233.     int  sort_cmp();
  234.     long *k_cnt;
  235.     char *k_dat;
  236.  
  237.  
  238.     if (sort_state != SORT_OPEN)
  239.         sort_error("Improper Record Release");
  240.  
  241.     bld_sort_key(data);
  242.  
  243.     sort_rec_cnt++;
  244.     sort_write(sfile1, data, sort_rec_size);
  245.  
  246.     k_cnt  = (long *) sbuf1.sb_radr;
  247.     k_dat  = sbuf1.sb_radr + sizeof(long);
  248.     *k_cnt = sort_rec_cnt;
  249.     memcpy(k_dat, sort_key_rec, sort_key_size);
  250.  
  251.     sbuf1.sb_rcnt++;
  252.         if (sbuf1.sb_rcnt < sbuf1.sb_rsiz)
  253.         sbuf1.sb_radr += sort_krec_size;
  254.     else
  255.     {    qsort(sbuf1.sb_badr, (int)sbuf1.sb_rcnt, sort_krec_size, sort_cmp);
  256.         sort_write(sfile2, (char *)&sbuf1.sb_rcnt, sizeof(long));
  257.         sort_write(sfile2, sbuf1.sb_badr, sbuf1.sb_rcnt*sort_krec_size);
  258.         sbuf1.sb_rcnt = 0;
  259.         sbuf1.sb_radr = sbuf1.sb_badr;
  260.     }
  261. }
  262.  
  263.  
  264.  
  265.  
  266. /*
  267.  *    sort_cmp  -  sort compare function
  268.  */
  269.  sort_cmp(s1,s2)
  270.   char *s1, *s2;
  271. {
  272.     return(memcmp(s1+sizeof(long),s2+sizeof(long),sort_key_size));
  273. }
  274.  
  275. /*
  276.  *    bld_sort_key  -  Build the sort key record
  277.  */
  278.  
  279. bld_sort_key(data)
  280.  char *data;
  281. {
  282.     struct key_field *f;
  283.     char *s,*d;
  284.     int  i, tmp, cmpl;
  285.  
  286.     d = sort_key_rec;
  287.     f = key_spec;     
  288.  
  289.     while (f)
  290.     {
  291.         s = data